package cn.blunce.TreeTest;


import java.util.LinkedList;
import java.util.Stack;


/**
 * Created by Experiment on 2016/3/25.
 *
 * @noinspection Since15
 */
public class TreeTest {

    public static String CreateTreeString(int level) {
        String tree = "[";
        for (int i = 1; i <= Math.pow(2.0, level) - 1; i++)
            tree += String.valueOf(i) + ",";
        tree = tree.substring(0, tree.length() - 1);
        return tree + "]";
    }

    public static void TreeCreateTest() {
        TreeNode root = new TreeNode("[1,2,3]");
        System.out.println(root.toString());
    }


    public static String PreTraverse(TreeNode root) {
        String tree = "[";
        Stack stack = new Stack();
        TreeNode point = root;
        while (point != null || !stack.empty()) {
            while (point != null) {
                //to do
                tree += String.valueOf(point.val) + ",";
                stack.push(point);
                point = point.left;
            }
            if (!stack.isEmpty()) {
                point = (TreeNode) stack.pop();
                point = point.right;
            }
        }
        return tree.substring(0, tree.length() - 1) + "]";
    }

    public static void PreTraverseTest() {
        TreeNode tree = new TreeNode(CreateTreeString(3));
        System.out.println(tree.toString());
        System.out.println(PreTraverse(tree));
    }

    public static String MidTraverse(TreeNode root) {
        String tree = "[";
        Stack stack = new Stack();
        TreeNode point = root;
        while (point != null || !stack.empty()) {
            while (point != null) {
                stack.push(point);
                point = point.left;
            }
            if (!stack.isEmpty()) {
                point = (TreeNode) stack.pop();
                //to do
                tree += String.valueOf(point.val) + ",";
                point = point.right;
            }
        }
        return tree.substring(0, tree.length() - 1) + "]";
    }

    public static void MidTraverseTest() {
        TreeNode tree = new TreeNode(CreateTreeString(3));
        System.out.println(tree.toString());
        System.out.println(MidTraverse(tree));
    }

    public static String PostTraverse(TreeNode root) {
        String tree = "[";
        Stack stack = new Stack();
        TreeNode point = root;
        TreeNode visited = null;
        while (point != null || !stack.empty()) {
            if (point != null) {
                stack.push(point);
                point = point.left;
            } else {
                point = (TreeNode) stack.peek();
                if (point.right == null || point.right == visited) {
                    //to do
                    tree += String.valueOf(point.val) + ",";

                    visited = point;
                    stack.pop();
                    point = null;
                } else
                    point = point.right;
            }
        }
        return tree.substring(0, tree.length() - 1) + "]";
    }

    public static void PostTraverseTest() {
        TreeNode tree = new TreeNode(CreateTreeString(3));
        System.out.println(tree.toString());
        System.out.println(PostTraverse(tree));
    }

    public void LevelTraverse(TreeNode root) {
        LinkedList queue = new LinkedList();
        TreeNode point = root;
        queue.add(point);
        while (!queue.isEmpty()) {
            point = (TreeNode) queue.remove();
            //to do
            if (point.left != null)
                queue.add(point.left);
            if (point.right != null)
                queue.add(point.right);
        }
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        else if (p != null && q != null) {
            if (p.val != q.val)
                return false;
            else {
                boolean left = isSameTree(p.left, q.left);
                boolean right = isSameTree(p.right, q.right);
                return left && right;
            }
        } else
            return false;
    }
}
